package com.mlamp;

import java.util.ArrayList;
import java.util.List;

public class 括号生成深度优先遍历递减 {

    public static void main(String[] args) {

        括号生成深度优先遍历递减 instance = new 括号生成深度优先遍历递减();
        List<String> strings = instance.generateParenthesis(2);
        for (String item : strings) System.out.println(item);
        System.out.println("生成3组有效括号");
        strings = instance.generateParenthesisC(3);
        for (String item : strings) {
            System.out.println(item);
        }


    }

    private static int index = 0;

    public List<String> generateParenthesis(int n) {
        //说明至少3个左右括号可以提供自由组合
        List<String> results = new ArrayList<>();
        dfs("", n, n, results);
        return results;
    }

    public List<String> generateParenthesisA(int n) {
        List<String> results = new ArrayList<>();
        dfsA("", n, n, results);
        return results;
    }

    public List<String> generateParenthesisC(int n) {
        List<String> results = new ArrayList<>();
        dfsC("", n, n, results);
        return results;
    }

    private void dfsA(String s, int left, int right, List<String> results) {

        if (left == 0 && right == 0) {
            results.add(s);
            return;
        }
        if (left > 0) {
            dfsA(s + "(", left + 1, right, results);
        }
        if (right > 0 && right > left) {
            dfsA(s + ")", left, right + 1, results);
        }

    }


    public List<String> generateParenthesis222(int n) {
        List<String> result = new ArrayList<>();
        dfs22("", n, n, result);
        return result;
    }

    private void dfs22(String s, int left, int right, List<String> result) {
        if (left == 0 && right == 0) {
            result.add(s);
            return;
        }
        if (left > 0) dfs22(s + "(", left - 1, right, result);
        if (right > left && right > 0) dfs22(s + ")", left, right, result);
    }


    private void dfs2(String s, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(s);
            return;
        }
        if (left > 0) {
            dfs(s + "(", left - 1, right, res);
        }
        if (right > 0 && right > left) {
            dfs(s + ")", left, right - 1, res);
        }
    }


    private void dfs3(String s, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(s);
            return;
        }
        if (left > 0) dfs3(s + "(", left - 1, right, res);
        if (right > left && right > 0) dfs3(s + ")", left, right - 1, res);
    }


    /**
     * 深度优先遍历
     *
     * @param s
     * @param left
     * @param right
     * @param results
     */

    private void dfs(String s, int left, int right, List<String> results) {
        if (left == 0 && right == 0) {
            results.add(s);
            return;
        }

        if (left > 0) {
            dfs(s + "(", left - 1, right, results);
        }

        if (right > 0 && left < right) {
            dfs(s + ")", left, right - 1, results);
        }

    }

    /**
     * 深度优先遍历
     */

    public void dfsC(String s, int left, int right, List<String> result) {
        if (left == 0 && right == 0) {
            result.add(s);
            return;
        }
        if (left > 0) {
            dfsC(s + "(", left - 1, right, result);
        }
        if (right > 0 && right > left) {
            dfs(s + ")", left, right - 1, result);
        }
    }
}
